package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/1 10:17
 * @description :5道
 * 厚积薄发。
 * persevere to last
 * 2021.11.1
 * 李红磊
 */
public class t20211101 {

    //面试题08.12 八皇后
    public List<List<String>> solveNQueens(int n) {
        ArrayList<List<String>> res = new ArrayList<>();
        if (n == 1) {
            List temp = new ArrayList<String>();
            temp.add("Q");
            res.add(temp);
            return res;
        }
        if (n < 4) {
            return res;
        }
        char[][] chess = new char[n][n];
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess.length; j++) {
                chess[i][j] = '.';
            }
        }


        dfs(chess, 0, res);
        return res;

    }

    /**
     * @Author 李红磊
     * @Date 2021/11/1 10:37
     * @param: chess 棋盘
     * @param: row 当前要往第row行放置【皇后】
     * @param: res 用于返回
     **/
    private void dfs(char[][] chess, int row, ArrayList<List<String>> res) {
        if (row == chess.length) {
            //表示最后一个皇后已经放置好了
            res.add(construct(chess));
            return;
        }

        //开始对第row行放置皇后

        //我们选择是在row行的哪一列进行放置
        for (int col = 0; col < chess.length; col++) {
            if (isValid(chess, row, col)) {
                //程序走到这里，证明 row行col列可以放置【皇后】
                chess[row][col] = 'Q';
                //本行已经放置了皇后
                //现在去下一行放置皇后
                dfs(chess, row + 1, res);
                chess[row][col] = '.';
            }


        }


    }

    private List<String> construct(char[][] chess) {
        ArrayList<String> temp = new ArrayList<>();
        for (int i = 0; i < chess.length; i++) {
            temp.add(new String(chess[i]));
        }
        return temp;
    }

    private boolean isValid(char[][] chess, int row, int col) {
        //判断在第row行col列放置皇后是否【合理】

        //我们不需要判断row这行上有没有皇后，因为我们每次只在一行放置一个皇后
        //判断col这一列上有没有皇后
        for (int i = 0; i < row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }

        //判断对角线上是否有皇后
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess.length; j++) {//通过斜率来判断对角线
                if (chess[i][j] == 'Q' && Math.abs(i - row) == Math.abs(j - col)) {
                    return false;
                }
            }
        }

        return true;
    }


    //572.分糖果
    public int distributeCandies(int[] candyType) {
        /*
        糖果数量 n 为偶数
        假设糖果种类数量为 mm，那么单份中可使得糖果种类数量最大为,n/2

        若m等于n/2，则最大值为n/2
        若m大约n/2，则最大值为n/2
        若m小于n/2，那最大值为m

         */
        HashSet<Integer> hashSet = new HashSet<>();

        Arrays.stream(candyType).forEach(item -> hashSet.add(item));

        return Math.min(hashSet.size(), candyType.length / 2);

    }


    //78.子集
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();

        backTrack(0, nums, res, new ArrayList<Integer>());

        return res;
    }

    private void backTrack(int i, int[] nums, ArrayList<List<Integer>> res, ArrayList<Integer> cur) {
        res.add(new ArrayList<>(cur));
        for (int j = i; j < nums.length; j++) {
            cur.add(nums[j]);
            backTrack(j + 1, nums, res, cur);
            cur.remove(cur.size() - 1);
        }

    }

    public List<String> solution(String str) {
        ArrayList<String> res = new ArrayList<>();

        boolean[] visit = new boolean[str.length()];

        dfs2(str, visit, "", res);

        return res;
    }

    private void dfs2(String str, boolean[] visit, String cur, ArrayList<String> res) {
        if (cur.length() == str.length()) {
            res.add(new String(cur));
            return;
        }


        for (int i = 0; i < str.length(); i++) {
            //剪枝
            if (i > 0 && str.charAt(i) == str.charAt(i - 1) && !visit[i - 1]) {
                continue;
            }

            if (!visit[i]) {
                visit[i] = true;
                dfs2(str, visit, cur + str.charAt(i), res);
                visit[i] = false;
            }
        }

    }

    //八皇后复习
    public List<List<String>> solveNQueens2(int n) {
        ArrayList<List<String>> res = new ArrayList<>();
        if (n == 1) {
            ArrayList<String> list = new ArrayList<>();
            list.add("Q");
            res.add(list);
            return res;
        }
        if (n < 4) {
            return res;
        }

        //模拟出棋盘
        char[][] chess = new char[n][n];
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess.length; j++) {
                chess[i][j] = '.';
            }
        }
        dfs3(chess, 0, res);

        return res;
    }

    private void dfs3(char[][] chess, int row, ArrayList<List<String>> res) {
        if (row == chess.length) {
            res.add(create(chess));
            return;
        }

        //开始在第row行放置皇后
        //寻找合适的列放置【皇后】
        for (int col = 0; col < chess.length; col++) {
            if (Vaild(chess, row, col)) {
                chess[row][col] = 'Q';
                dfs3(chess, row + 1, res);
                chess[row][col] = '.';
            }

        }


    }

    private boolean Vaild(char[][] chess, int row, int col) {
        //判断row行col列是否可以放置皇后

        //判断这一列有无皇后
        for (int i = 0; i < row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }

        //判断对角线
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess.length; j++) {
                if (chess[i][j] == 'Q' && (Math.abs(i - row)) == Math.abs(j - col)) {
                    return false;
                }
            }
        }

        return true;
    }

    private List<String> create(char[][] chess) {
        ArrayList<String> temp = new ArrayList<>();
        for (int i = 0; i < chess.length; i++) {
            temp.add(new String(chess[i]));
        }
        return temp;
    }

    //90.子集||
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();

        boolean[] visit = new boolean[nums.length];
        Arrays.sort(nums);

        backTrack2(nums, 0, res, new ArrayList<Integer>(), visit);
        return res;

    }

    private void backTrack2(int[] nums, int i, ArrayList<List<Integer>> res, ArrayList<Integer> cur, boolean[] visit) {
        res.add(new ArrayList<>(cur));

        for (int j = i; j < nums.length; j++) {

            //剪枝
            if (j > 0 && nums[j - 1] == nums[j] && !visit[j - 1]) {
                continue;
            }

            visit[j] = true;
            cur.add(nums[j]);
            backTrack2(nums, j + 1, res, cur, visit);
            visit[j] = false;
            cur.remove(cur.size() - 1);


        }


    }


    //面试题08.13 堆箱子
    public int pileBox(int[][] box) {

        Arrays.sort(box, (a, b) -> a[0] - b[0]);
        int[] f = new int[box.length];
        f[0] = box[0][2];//f[i]表示前i个箱子可以形成的最大高度
        int max = f[0];


        for (int i = 1; i < box.length; i++) {
            int wi = box[i][0], di = box[i][1], hi = box[i][2];
            f[i] = hi;

            for (int j = 0; j < i; j++) {
                int wj = box[j][0], dj = box[j][1], hj = box[j][2];
                if (wi > wj && di > dj && hi > hj) {
                    f[i] = Math.max(f[j] + hi, f[i]);
                }

            }
            max = Math.max(max, f[i]);
        }


        return max;
    }


    public static void main(String[] args) {
        t20211101 t20211101 = new t20211101();


        int[][] arr = {
                {1, 1, 1},
                {2, 3, 4},
                {2, 6, 7},
                {3, 4, 5}
        };


    }

}
